/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * <p>
 * 区间的合并
 *  Given [1,3],[2,6],[8,10],[15,18], 
 *  return [1,6],[8,10],[15,18].
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月21日
 */
public class MergeIntervals {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        if(intervals==null || intervals.isEmpty()){
            return result;
        }
        Comparator<Interval> comparator = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start<o2.start){
                    return -1;
                }else if(o1.start>o2.start){
                    return 1;
                }else{
                    //start相同，需要比较end
                    if(o1.end<o2.end){
                        return -1;
                    }else if(o1.end>o2.end){
                        return 1;
                    }else{
                        return 0;
                    }
                }
            }
        };
        Collections.sort(intervals, comparator);
        for(int i=0;i<intervals.size();i++){
            Interval current = intervals.get(i);
            if(result.isEmpty()){
                //初始化结果集
                result.add(current);
            }else{
                Interval last = result.get(result.size()-1);
                if(last.end>=current.start){
                    //合并并更新结果集
                    last.end = Math.max(last.end, current.end);
                }else{
                    result.add(current);
                }
            }
        }
        return result;
    }
}
